use rand::Rng;

fn mod_exp(mut base: u128, mut exp: u128, modulus: u128) -> u128 {
    let mut result = 1;
    base = base % modulus;

    while exp > 0{
        if exp & 1 == 1 {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp = exp >> 1;
    }
    result
}

fn decompose(n: u128) -> (u128, u128) {
    let mut d = n - 1;
    let mut r = 0;

    while d % 2 == 0 {
        d /= 2;
        r += 1;
    }
    (d, r)
}

fn miller_rabin_test(n: u128, a: u128, d: u128, r: u128) -> bool {
    let mut x = mod_exp(a, d, n);
    if x == 1 || x == n - 1 {
        return true;
    }

    for _ in 0..r - 1 {
        x = mod_exp(x, 2, n);
        if x == n - 1 {
            return true;
        }
    }
    false
}

const BASIC_PRIME : [u128; 10] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];

fn is_prime(n: u128, k: u32) -> bool {
    if n <= 1 {
        return false;
    }
    for &p in BASIC_PRIME.iter() {
        if n == p {
            return true;
        }
        if n % p == 0 {
            return false;
        }
    }

    let (d, r) = decompose(n);

    let mut rng = rand::thread_rng();
    for _ in 0..k {
        let a = rng.gen_range(2..n - 1);
        if !miller_rabin_test(n, a, d, r) {
            return false;
        }
    }
    true
}

pub fn min_edge_prime_num(number: u32) -> String {
    let threshold = number as u128;
    let mut side_length: u128 = 1;
    let mut prime_count: u128 = 0;
    let mut total_count: u128 = 1;

    loop {
        side_length += 2;
        let mut corner = [0; 4];
        for i in 0..4 {
            corner[i] = side_length * side_length - i as u128 * (side_length - 1);
            if is_prime(corner[i], 10) {
                prime_count += 1;
            }
        }
        total_count += 4;

        if prime_count * 100 < threshold * total_count {
            break;
        }
    }
    format!("{},{}", side_length, prime_count)
}
